//
// Created by zhulingfeng on 2020/4/12.
//

#include "subsets.hpp"
#include <algorithm>
/** DFS+回溯（剪枝）**/
void SubsetsWithDFSAndPrune(std::vector<int>& a,
                            std::vector<std::vector<int>>& res,
                            std::vector<int>& cur, int i) {
  res.push_back(
      cur);  // without a[i], 同时剪枝, 剪去对当前结点一直沿左子树递归的路径
  for (int j = i; j < a.size(); j++) {  // 对剪枝路径上每一个右子树的递归
    cur.push_back(a[j]);
    SubsetsWithDFSAndPrune(a, res, cur, j + 1);
    cur.pop_back();
  }
}
/** 传引用 **/
void SubsetsWithBinaryTreeTraversal2(std::vector<int>& a,
                                     std::vector<std::vector<int>>& res,
                                     std::vector<int>& cur, int i) {
  if (i >= a.size()) {
    res.push_back(cur);
    return;
  }
  // without a[i]，相当于递归左子树
  SubsetsWithBinaryTreeTraversal2(a, res, cur, i + 1);
  cur.push_back(a[i]);
  // with a[i], 相当于递归右子树
  SubsetsWithBinaryTreeTraversal2(a, res, cur, i + 1);
  cur.pop_back();  // 由于传引用，返回上一层前，把a[i]删除
}
/** 传值 **/
void SubsetsWithBinaryTreeTraversal1(std::vector<int>& a,
                                     std::vector<std::vector<int>>& res,
                                     std::vector<int> cur, int i) {
  if (i >= a.size()) {
    res.push_back(cur);
    return;
  }
  // without a[i]，相当于递归左子树
  SubsetsWithBinaryTreeTraversal1(a, res, cur, i + 1);
  cur.push_back(a[i]);
  // with a[i], 相当于递归右子树
  SubsetsWithBinaryTreeTraversal1(a, res, cur, i + 1);
}
std::vector<std::vector<int>> Subsets(std::vector<int>& nums) {
  // sort(nums.begin(), nums.end()); // 不必排序
  std::vector<std::vector<int>> res;
  std::vector<int> cur;
  SubsetsWithDFSAndPrune(nums, res, cur, 0);
  return res;
}

/** DFS+回溯（剪枝）**/
void SubsetsWithDup(std::vector<int>& a, std::vector<std::vector<int>>& res,
                    std::vector<int>& cur, int i) {
  res.push_back(
      cur);  // without a[i], 同时剪枝, 剪去对当前结点一直沿左子树递归的路径
  for (int j = i; j < a.size(); j++) {  // 对剪枝路径上每一个右子树的递归
    // 简直路径上的右子树根结点，除第一个外，如与上一个的值相同，则遍历结果重复，剪枝
    if (j > i && a[j] == a[j - 1]) continue;
    cur.push_back(a[j]);
    SubsetsWithDup(a, res, cur, j + 1);
    cur.pop_back();
  }
}

std::vector<std::vector<int>> SubsetsWithDup(std::vector<int>& nums) {
  std::sort(nums.begin(), nums.end());  // 必须排序
  std::vector<std::vector<int>> res;
  std::vector<int> cur;
  SubsetsWithDup(nums, res, cur, 0);
  return res;
}
